package ljl.codetop300;

/**
 * 真的难，做了 4 遍了还是不会
 */
public class _offer_51_reverse_pairs {

  class lu_fei {
    int[] nums, tmp;
    public int reversePairs(int[] nums) {
      this.nums = nums;
      tmp = new int[nums.length];
      return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
      if (l >= r) return 0;
      int m = (l + r) / 2;
      int res = mergeSort(l, m) + mergeSort(m + 1, r);
      int i = l, j = m + 1;
      for (int k = l; k <= r; k++)
        tmp[k] = nums[k];
      for (int k = l; k <= r; k++) {
        if (i == m + 1)
          nums[k] = tmp[j++];
        else if (j == r + 1 || tmp[i] <= tmp[j])
          nums[k] = tmp[i++];
        else {
          nums[k] = tmp[j++];
          // 最难想的是这一行，我是想不到反正
          res += m - i + 1;
        }
      }
      return res;
    }
  }

  static class test {
    public int reversePairs(int[] nums) {
      return merge(nums, nums.clone(), 0, nums.length - 1);
    }
    int merge(int[] nums, int[] tmp, int from, int to) {
      if (from >= to) return 0;
      int mid = (from + to) >>> 1;
      int res = merge(nums, tmp, from, mid) + merge(nums, tmp, mid + 1, to);
      System.arraycopy(nums, from, tmp, from, to + 1 - from);
      int i = from;
      int j = mid + 1;
      for (int k = from; k <= to; k++) {
        if (i == mid + 1) nums[k] = tmp[j++];
        else if (j == to + 1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++];
        else {
          nums[k] = tmp[j++];
          res += mid - i + 1;
        }
      }
      return res;
    }
  }
}
